Implementing a simple LRU Cache

Problem:

LRU Cache with a maximum capacity (http://en.wikipedia.org/wiki/Cache_algorithms)
Set, Get, Delete operations O(1) (amortized, depends on Python's dict implementation)
Access by key
Set and Get move the element back to the most recent
If the cache is full, adding a new values drops the oldest item
Assume no one is crazy enough to create a LRUCache with capacity = 1

Today I decided to challenge myself and implement a LRU Cache in 25 minutes (Pomodoro FTW).
Quick brainstorm and decided to go with a double linked list and a dict (for _key => listnode).

The basic idea is:

All operations get a reference to the node via the dict
Set and Get delete the node and re-add it to the top
If Set is called with a new key and the cache is full, delete the last item
Delete simply deletes the node

After implementing the whole thing I realise, wait, isn't collections.OrderedDict just that?

Here's a simple LRU Cache.



In [83]:

    
from collections import OrderedDict

class LRUCache(object):
    """Implementation of a LRU Cache. Iterating goes from oldest to newest."""
    
    def __init__(self, capacity):
        self._cache_impl = OrderedDict()
        # calling self.items to count isn't O(1)
        self._count = 0
        # A simple maximum number of items
        self._capacity = capacity
        
    def __setitem__(self, key, value):
        """Set the value for the key and move it to the most recent.
        If the cache is full, delete the oldest item.
        """
        if key in self._cache_impl:
            del self._cache_impl[key]
        elif self.full():
            # last=False because inserting a new key adds to the end
            self._cache_impl.popitem(last=False)
        else:
            self._count += 1
        self._cache_impl[key] = value
        
    def __getitem__(self, key):
        """Get the value for the key and move it to the most recent."""
        value = self._cache_impl[key]
        del self._cache_impl[key]
        self._cache_impl[key] = value
        return value
    
    def __delitem__(self, key):
        del self._cache_impl[key]
        self._count -= 1
    
    def full(self):
        return self._count == self._capacity
    
    def values(self):
        return self._cache_impl.values()

And here's a simple test:



In [96]:

    
def test_cache():
    cache = LRUCache(2)
    cache['spoing'] = 1
    cache['boing'] = 2
    assert cache.values() == [1,2]
    assert cache['spoing'] == 1
    assert cache.values() == [2,1]
    cache['boom'] = 3
    assert cache.values() == [1,3]
    
    cache = LRUCache(3)
    cache['spoing'] = 1
    cache['boing'] = 2
    assert cache.values() == [1,2]
    assert cache['spoing'] == 1
    assert cache.values() == [2,1]
    cache['boom'] = 3
    assert cache.values() == [2,1,3]
    cache['spoing'] = 4
    assert cache.values() == [2,3,4]

I really love python!



In [ ]: